#include "string_array.h"

using namespace std;

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];
    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
    {
        if(next[i] == -1)
            cout << 0;
        else
            cout << (next[i] + 1);
    }
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
    {
        if(nextVal[i] == -1)
            cout << 0;
        else
            cout << (nextVal[i] + 1);
    }
    cout << endl;
}

// 默认构造函数
myMatrix::myMatrix()
{
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    nodeList = nullptr;
}

// 带参数的构造函数
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* data)
{
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    
    if(nNum > 0 && data != nullptr)
    {
        nodeList = new matrixNode[nNum];
        // 从数组中读取三元组数据，每3个数一组：(row, col, value)
        for(int i = 0; i < nNum; i++)
        {
            nodeList[i].row = data[i * 3];
            nodeList[i].col = data[i * 3 + 1];
            nodeList[i].value = data[i * 3 + 2];
        }
    }
    else
    {
        nodeList = nullptr;
    }
}

// 析构函数
myMatrix::~myMatrix()
{
    if(nodeList != nullptr)
    {
        delete[] nodeList;
        nodeList = nullptr;
    }
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

// 快速转置算法
void myMatrix::FastTransposeSMatrix(myMatrix& T)
{
    // 转置后的矩阵：行数=原列数，列数=原行数，元素个数不变
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    
    if(nodeNum == 0)
    {
        T.nodeList = nullptr;
        return;
    }
    
    // 分配转置后的三元组数组
    if(T.nodeList != nullptr)
        delete[] T.nodeList;
    T.nodeList = new matrixNode[nodeNum];
    
    // 统计每一列（转置后的行）的非零元素个数
    int* num = new int[colNum]();  // 初始化为0
    for(int i = 0; i < nodeNum; i++)
    {
        num[nodeList[i].col]++;
    }
    
    // 计算每一列（转置后的行）的第一个非零元素在转置矩阵中的位置
    int* cpot = new int[colNum];
    cpot[0] = 0;
    for(int i = 1; i < colNum; i++)
    {
        cpot[i] = cpot[i - 1] + num[i - 1];
    }
    
    // 将原矩阵的三元组转置后放入转置矩阵
    for(int i = 0; i < nodeNum; i++)
    {
        int col = nodeList[i].col;  // 原矩阵的列号
        int pos = cpot[col];        // 在转置矩阵中的位置
        
        T.nodeList[pos].row = nodeList[i].col;    // 转置：行=原列
        T.nodeList[pos].col = nodeList[i].row;    // 转置：列=原行
        T.nodeList[pos].value = nodeList[i].value;
        
        cpot[col]++;  // 该列的下一个位置
    }
    
    // 释放临时数组
    delete[] num;
    delete[] cpot;
}

myStr::myStr(const char* str)
{
    if (str == nullptr) {
        length = 0;
        data = new char[1];
        data[0] = '\0';
        next = nullptr;
        nextVal = nullptr;
        return;
    }

    length = 0;
    while (str[length] != '\0')
        length++;

    data = new char[length + 1];
    for (int i = 0; i < length; i++)
        data[i] = str[i];
    data[length] = '\0';  // 添加结束符

    next = new int[length]();     // 零初始化
    nextVal = new int[length]();  // 零初始化
}

myStr::~myStr()
{
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

bool replaceStr(myStr& S,const int& start,const myStr& T,const myStr& V)
{
    if(start < 0 || start >= S.length || T.length == 0)
        return false;

    // 从 start 位置开始查找 T
    int pos = -1;
    for(int i = start; i <= S.length - T.length; i++)
    {
        bool match = true;
        for(int j = 0; j < T.length; j++)
        {
            if(S.data[i + j] != T.data[j])
            {
                match = false;
                break;
            }
        }
        if(match)
        {
            pos = i;
            break;
        }
    }

    if(pos == -1)
        return false;

    int newLength = S.length - T.length + V.length;
    char* newData = new char[newLength + 1];

    for(int i = 0; i < pos; i++)
        newData[i] = S.data[i];

    for(int i = 0; i < V.length; i++)
        newData[pos + i] = V.data[i];

    for(int i = pos + T.length; i < S.length; i++)
        newData[i - T.length + V.length] = S.data[i];
    
    newData[newLength] = '\0';  // 添加字符串结束符

    delete[] S.data;
    S.data = newData;
    S.length = newLength;

    delete[] S.next;
    delete[] S.nextVal;
    S.next = new int[newLength]();     // 零初始化
    S.nextVal = new int[newLength]();  // 零初始化

    return true;
}

void myStr::kmp_next()
{
    if (length == 0) return;
    
    int j = 0;
    int k = -1;
    next[0] = -1;

    while(j < length - 1)
    {
        if(k == -1 || data[j] == data[k])
        {
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
    
}

void myStr::kmp_nextVal() {
    if (length == 0) return;
    
    int j = 0, k = -1;
    nextVal[0] = -1;
    while (j < length - 1) {
        if (k == -1 || data[j] == data[k]) {
            j++; k++;
            if (j < length) {  // 防越界
                nextVal[j] = (data[j] != data[k]) ? k : nextVal[k];
            }
        } else {
            k = nextVal[k];
        }
    }
}

int simpleMatch(const myStr& S,const myStr& T)
{
    int i = 0;
    int j = 0;

    while(i < S.length && j < T.length)
    {
        if(S.data[i] == T.data[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if(j >= T.length)
        return i - T.length + 1;  // 从1开始计数
    else
        return -1;
}   

int kmpMatch(const myStr& S,const myStr& T)
{
    if (T.length == 0 || S.length == 0 || T.length > S.length) {
        return -1;
    }
    
    // 创建临时对象并计算nextVal
    myStr tempPattern(T);
    tempPattern.kmp_nextVal();
    
    int i = 0;
    int j = 0;

    while(i < S.length && j < T.length)
    {
        if(j == -1 || S.data[i] == T.data[j])
        {
            i++;
            j++;
        }
        else
            j = tempPattern.nextVal[j];
    }

    if(j >= T.length)
        return i - T.length + 1;  // 从1开始计数
    else
        return -1;
}

// 补充的构造函数，保持与原文件兼容

// myStr整数构造函数（创建指定长度的空字符串）
myStr::myStr(const int& len) {
    if (len <= 0) {
        data = nullptr;
        length = 0;
        next = nullptr;
        nextVal = nullptr;
        return;
    }
    
    length = len;
    data = new char[length + 1];
    
    // 初始化为空字符串
    for (int i = 0; i < length; i++) {
        data[i] = '\0';
    }
    data[length] = '\0';
    
    next = new int[length];
    nextVal = new int[length];
    
    // 初始化next和nextVal数组
    for (int i = 0; i < length; i++) {
        next[i] = 0;
        nextVal[i] = 0;
    }
}

// myStr复制构造函数
myStr::myStr(const myStr& other) {
    if (other.data == nullptr || other.length == 0) {
        data = nullptr;
        length = 0;
        next = nullptr;
        nextVal = nullptr;
        return;
    }
    
    length = other.length;
    data = new char[length + 1];
    
    // 复制数据
    for (int i = 0; i < length; i++) {
        data[i] = other.data[i];
    }
    data[length] = '\0';
    
    next = new int[length];
    nextVal = new int[length];
    
    // 复制next和nextVal数组
    for (int i = 0; i < length; i++) {
        next[i] = other.next[i];
        nextVal[i] = other.nextVal[i];
    }
}

// myMatrix复制构造函数
myMatrix::myMatrix(const myMatrix& other) {
    rowNum = other.rowNum;
    colNum = other.colNum;
    nodeNum = other.nodeNum;
    
    if (nodeNum == 0 || other.nodeList == nullptr) {
        nodeList = nullptr;
        return;
    }
    
    nodeList = new matrixNode[nodeNum];
    
    // 复制所有节点
    for (int i = 0; i < nodeNum; i++) {
        nodeList[i].row = other.nodeList[i].row;
        nodeList[i].col = other.nodeList[i].col;
        nodeList[i].value = other.nodeList[i].value;
    }
}
